package cn.suchan.jianzhi.q8_jumpfloor;

/**
 * 知识点：跳台阶
 * 题目描述
 * 一只青蛙一次可以跳上1级台阶，也可以跳上2级。
 * 求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
 *
 * @author suchan
 * @date 2019/05/23
 */
public class Solution {

    /**
     * 由于一步最多走连两个台阶，因此要到达第N级台阶，有两种方案：
     * <p>
     * ①走到第N-1级台阶上，然后走1级台阶跨到最上方；
     * ②走到第N-2级台阶上，然后一步走两级台阶跨到最上方。注意，从第N-2级台阶走1级到N-1级台阶这种情况已经计算在第一种情况中计算过了。
     * <p>
     * 我们用a(N-1)和a(N-2)分别表示走到第N-1级和第N-2级台阶的方法数，那么走到第N级台阶的方法数就是：
     * <p>
     * a(N)= a(N-1)+ a(N-2)
     * <p>
     * 显然，这就是斐波那契数列的递推公式，因此走台阶问题的解刚好是斐波那契数列。
     *
     * @param target
     * @return
     */
    public int JumpFloor(int target) {
        // F(0)=0，F(1)=1
        if (target == 0 || target == 1) {
            return 1;
        }
        // F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）
        int[] jumpArray = new int[40];
        jumpArray[0] = 1;
        jumpArray[1] = 1;
        for (int i = 2; i <= target; i++) {
            jumpArray[i] = jumpArray[i - 1] + jumpArray[i - 2];
        }
        return jumpArray[target];
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        int jumpFloor = solution.JumpFloor(2);
        System.out.println("jumpFloor==>" + jumpFloor);
    }
}
